package com.justnow.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * 141.环形链表
 */
public class Solution141 {

    /**
     * 方法一，往hashset中添加元素，在插入前判断是否存在重复的元素，如果存在
     * 那么说明存在环，否则失败。
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            } else {
                set.add(head);
                head = head.next;
            }
        }

        return false;
    }

    /**
     * 方法二，双指针追击法，基本思想是在环道中，快的绕了一圈总可以追上慢的；但是直道上却不会出现这些问题
     * @param head
     * @return
     */
    public boolean hashCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head.next;
        ListNode slow = head;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }

            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}